package BinaryTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * The type Binary tree traversal.
 * 二叉树遍历的迭代法
 * 利用栈
 */
class BinaryTreeTraversal {

    /**
     * 迭代法 前序遍历
     * 前序遍历是中左右，每次先处理的是中间节点，
     * 那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
     * */
    static List<Integer> preOrderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();  //遍历收集
        Stack<TreeNode> stack = new Stack<>();  //栈的利用

        if(root==null){
            return null;
        }
        //根节点先入栈
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode currNode = stack.pop();
            res.add(currNode.val);
            //如果右和左子节点不为空，则入栈
            if(currNode.right != null){
                stack.push(currNode.right);
            }
            if(currNode.left != null){
                stack.push(currNode.left);
            }
        }
        return res;
    }

    /**
     * 中序遍历  ，左中右
     * 首先中序逻辑是从当前节点一直往左走到底，如果左节点为空，则获取当前节点值，
     * 并返回上层访问父节点的值，再从右节点开始，依次循环
     * */
    static List<Integer> inOrderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();  //遍历收集
        Stack<TreeNode> stack = new Stack<>();  //栈的利用

        if(root==null) {
            return null;
        }
        TreeNode cur = root;
        while(cur!=null || !stack.isEmpty()){

            //沿当前节点一直遍历左节点，直到该节点没有左节点
            if(cur !=null){
                stack.push(cur);
                cur = cur.left;
            }else{
                //出栈的即当前节点的上一节点,访问数据
                cur = stack.pop();
                //获取当前节点值
                res.add(cur.val);
                cur = cur.right;
            }
        }

        return res;
    }


    /**
     * 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左
     * 前序遍历先右后左 最后翻转结果
     * */
    static List<Integer> postOrderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();  //遍历收集
        Stack<TreeNode> stack = new Stack<>();  //栈的利用

        if(root==null){
            return null;
        }
        //根节点先入栈
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode currNode = stack.pop();
            res.add(currNode.val);
            //如果左和右子节点不为空，则入栈
            if(currNode.left != null){
                stack.push(currNode.left);
            }

            if(currNode.right != null){
                stack.push(currNode.right);
            }

        }
        Collections.reverse(res);
        return res;
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(1);
        root.left = node1;
        root.right = node4;
        node1.left = node2;
        node1.right = node3;
        System.out.println(preOrderTraversal(root));
        System.out.println(inOrderTraversal(root));
        System.out.println(postOrderTraversal(root));
    }
}
